#include <vector>
#include <string>
#include <algorithm>

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

using std::vector;
using std::string;
using std::binary_search;

static vector<string> dictionary;
static int len;

string word;

static const int BUF_SIZE = 32;

static int wordLen;

bool comp(const string &str1, const string &str2) {
  int length = word.size();
  if (str1 == word) {
    for (int i = 0; i < length; ++i) {
      if (str2[i] != word[i]) {
        return str2[i] > word[i];
      }
    }
  } else {
    for (int i = 0; i < length; ++i) {
      if (str1[i] != word[i]) {
        return str1[i] < word[i];
      }
    }
  }
  return false;
}

void getRange(string &str, int &start, int &end) {
  start = -1;
  end = -1;
  word = str;
  if (binary_search(dictionary.begin(), dictionary.end(), word, comp)) {
    int length = word.size();
    for (int i = 0; i < len; ++i) {
      bool match = false;;
      for (int j = 0; j < length; ++j) {
        if (dictionary[i][j] != word[j]) {
          match = true;
          break;
        }
      }

      /* Found match */
      if (match) {
        if (start != -1) {
          start = i;
        }
        end = i;
      }
    }
  }
}

/**
 * @brief A valid state is one where words of that type exist.
 *
 *
 */
bool validState(int *state, int depth) {
  int index = 0;
  while (index < wordLen) {
    /* Check this column (add letters of words) */
    int i;
    word.clear();
    for (i = 0; i < depth; ++i) {
      word += dictionary[state[i]][index];
    }

    /* If we don't find it then return false */
    if (!binary_search(dictionary.begin(), dictionary.end(), word, comp)) {
      return false;
    }
    index++;
  }

  return true;
}

void backtrack(int index, int *state) {
  /* Check prunning */
  if (!validState(state, index)) {
    return;
  }

  if (index == wordLen) {
    /* Found one! */
    printf("\nANSWER!!!\n");
    for (int i = 0; i < wordLen; ++i) {
      printf("%s\n", dictionary[state[i]].c_str());
    }
    printf("\n");
    exit(0);
  }

  /* We are on a valid state, lets check all our possibilities */
  for (int i = 0; i < len; ++i) {
    state[index] = i;
    backtrack(index + 1, state);
  }
}

int main(int argc, char **argv) {
  char buf[BUF_SIZE];
  FILE *dict;

  /* Check args */
  if (argc != 3) {
    printf("USAGE: %s <word length> <dictionary file>\n", argv[0]);
    return -1;
  }

  /* Read dictionary */
  dict = fopen(argv[2], "r");
  if (dict == NULL) {
    printf("Couldn't open dictionary file for reading\n");
    return -1;
  }
  while (fgets(buf, BUF_SIZE, dict) != NULL) {
    dictionary.push_back(string(buf));
  }
  len = dictionary.size();

  wordLen = strtol(argv[1], NULL, 10);
  word.reserve(wordLen + 1);

  /* Create the state tracker */
  int *state = new int[wordLen];
  for (int i = 0; i < wordLen; i++) {
    state[i] = -1;
  }

  /* Processing */
  printf("\n");
  for (int i = 0; i < len; ++i) {
    struct timeval tv1;
    struct timeval tv2;
    uint32_t secs;
    uint32_t usecs;
    state[0] = i;
    gettimeofday(&tv1, NULL);
    backtrack(1, state);
    gettimeofday(&tv2, NULL);

    /* Timing */
    if (tv2.tv_sec > tv1.tv_sec) {
      tv1.tv_sec--;
      tv2.tv_usec += 1000000;
    }
    secs = tv2.tv_sec - tv1.tv_sec;
    usecs = tv2.tv_usec - tv1.tv_usec;
    printf("\rProgress: %d of %d - %u.%03us", i, len, secs, usecs / 1000);
    fflush(stdout);
  }

  printf("\n\nNo solution\n");

  delete[] state;

  return 0;
}
